//输入一个链表，输出该链表中倒数第k个结点。
//
//示例1
//输入：
//1, { 1,2,3,4,5 }
//复制返回值：
//{ 5 }


//对于这种计算第k个节点的问题可以统一先遍历整个链表，计算链表中所有元素的个数
//
//同时需要考虑①链表为空的情况②输入k与链表节点总数的关系，k<0或k>nums的情况都要返回空

#include<stdio.h>


struct ListNode
{
    int val;
    struct ListNode* next;
};

//循环遍历法
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    if (pListHead == NULL)
    {
        return NULL;
    }
    // write code here
    int nums = 1;
    struct ListNode* cur = pListHead;
    while (cur->next)
    {
        nums++;
        cur = cur->next;
    }
    if (k > nums || k < 0)
    {
        return NULL;
    }
    struct ListNode* returnode = pListHead;
    for (int i = 0; i < nums - k; i++)
    {
        returnode = returnode->next;
    }
    return returnode;
}



//快慢指针法
//①间隔k个节点
//设置一个slow指针，一个fast指针。假设k = 2，那么就令fast指向slow两个节点前的位置。从而使得slow与fast之间的距离保持为k个结点数。
//最终当fast走到空时，slow指向倒数第k个节点。
// 
//②间隔k - 1个节点
//同理，最终当fast走到尾结点时，slow指向倒数k个节点

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    if (pListHead == NULL)
    {
        return NULL;
    }
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    for (int i = k; i > 0; i--)
    {
        if (fast == NULL)//考虑如果链表没有k长
        {
            return NULL;
        }
        fast = fast->next;
    }
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}